// Copyright (C) 2024 Kumo inc.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//

#pragma once

#include <cassert>
#include <chrono>
#include <cstddef>
#include <functional>
#include <iterator>
#include <list>
#include <stdexcept>
#include <unordered_map>

#include <deneb/cache_tags.h>
#include <deneb/error.h>
#include <deneb/internal/base_cache.h>
#include <deneb/internal/information.h>
#include <deneb/internal/last_accessed.h>

namespace deneb {

    namespace internal {
        template<typename Key,
                typename Value,
                typename HashFunction,
                typename KeyEqual>
        using UntimedCacheBase = internal::BaseCache<Key,
                Value,
                internal::Information,
                HashFunction,
                KeyEqual,
                deneb_tag::BasicCache>;
    }  // namespace internal

    /// A basic LRU cache implementation.
    ///
    /// An LRU cache is a fixed-size cache that remembers the order in which
    /// elements were inserted into it. When the size of the cache exceeds its
    /// capacity, the "least-recently-used" (LRU) element is erased. In our
    /// implementation, usage is defined as insertion, but not lookup. That is,
    /// looking up an element does not move it to the "front" of the cache (making
    /// the operation faster). Only insertions (and erasures) can change the order
    /// of elements. The capacity of the cache can be modified at any time.
    ///
    /// \see deneb::TimedCache
    template<typename Key,
            typename Value,
            typename HashFunction = std::hash<Key>,
            typename KeyEqual = std::equal_to<Key>>
    class Cache
            : public internal::UntimedCacheBase<Key, Value, HashFunction, KeyEqual> {
    private:
        using super = internal::UntimedCacheBase<Key, Value, HashFunction, KeyEqual>;
        using PRIVATE_BASE_CACHE_MEMBERS;

    public:
        using PUBLIC_BASE_CACHE_MEMBERS;
        using typename super::size_t;

        /// \copydoc BaseCache::BaseCache(size_t,const HashFunction&,const KeyEqual&)
        /// \detailss The capacity defaults to an internal constant, currently 128.
        explicit Cache(size_t capacity = internal::DEFAULT_CAPACITY,
                       const HashFunction &hash = HashFunction(),
                       const KeyEqual &equal = KeyEqual())
                : super(capacity, hash, equal) {
        }

        /// \copydoc BaseCache(size_t,Iterator,Iterator,const HashFunction&,const
        /// KeyEqual&)
        template<typename Iterator>
        Cache(size_t capacity,
              Iterator begin,
              Iterator end,
              const HashFunction &hash = HashFunction(),
              const KeyEqual &equal = KeyEqual())
                : super(capacity, begin, end, hash, equal) {
        }

        /// \copydoc BaseCache(Iterator,Iterator,const HashFunction&,const
        /// KeyEqual&)
        template<typename Iterator>
        Cache(Iterator begin,
              Iterator end,
              const HashFunction &hash = HashFunction(),
              const KeyEqual &equal = KeyEqual())
                : super(begin, end, hash, equal) {
        }

        /// Constructor.
        ///
        /// \param capacity The capacity of the cache.
        /// \param range A range to construct the cache with.
        /// \param hash The hash function to use for the internal map.
        /// \param key_equal The key equality function to use for the internal map.
        template<typename Range, typename = internal::enable_if_range<Range>>
        Cache(size_t capacity,
              Range &&range,
              const HashFunction &hash = HashFunction(),
              const KeyEqual &equal = KeyEqual())
                : super(capacity, std::forward<Range>(range), hash, equal) {
        }

        /// Constructor.
        ///
        /// \param range A range to construct the cache with.
        /// \param hash The hash function to use for the internal map.
        /// \param key_equal The key equality function to use for the internal map.
        template<typename Range, typename = internal::enable_if_range<Range>>
        explicit Cache(Range &&range,
                       const HashFunction &hash = HashFunction(),
                       const KeyEqual &equal = KeyEqual())
                : super(std::forward<Range>(range), hash, equal) {
        }

        /// \copydoc BaseCache(InitializerList,const HashFunction&,const
        /// KeyEqual&)
        Cache(InitializerList list,
              const HashFunction &hash = HashFunction(),
              const KeyEqual &equal = KeyEqual())  // NOLINT(runtime/explicit)
                : super(list, hash, equal) {
        }

        /// \copydoc BaseCache(size_t,InitializerList,const HashFunction&,const
        /// KeyEqual&)
        Cache(size_t capacity,
              InitializerList list,
              const HashFunction &hash = HashFunction(),
              const KeyEqual &equal = KeyEqual())  // NOLINT(runtime/explicit)
                : super(capacity, list, hash, equal) {
        }

        /// \copydoc BaseCache::find(const Key&)
        UnorderedIterator find(const Key &key) override {
            auto iterator = _map.find(key);
            if (iterator != _map.end()) {
                _register_hit(key, iterator->second.value);
                _move_to_front(iterator->second.order);
                _last_accessed = iterator;
            } else {
                _register_miss(key);
            }

            return {*this, iterator};
        }

        /// \copydoc BaseCache::find(const Key&) const
        UnorderedConstIterator find(const Key &key) const override {
            auto iterator = _map.find(key);
            if (iterator != _map.end()) {
                _register_hit(key, iterator->second.value);
                _move_to_front(iterator->second.order);
                _last_accessed = iterator;
            } else {
                _register_miss(key);
            }

            return {*this, iterator};
        }

        /// \returns The most-recently inserted element.
        const Key &front() const noexcept {
            if (is_empty()) {
                throw deneb::deneb_error::EmptyCache("front");
            } else {
                // The queue is reversed for natural order of iteration.
                return _order.back();
            }
        }

        /// \returns The least-recently inserted element.
        const Key &back() const noexcept {
            if (is_empty()) {
                throw deneb::deneb_error::EmptyCache("back");
            } else {
                // The queue is reversed for natural order of iteration.
                return _order.front();
            }
        }
    };

}  // namespace deneb
